Graphs are powerful tools for a wide range of real applications, from biological and chemical databases, social networks, citation networks to information networks. Large graph data repositories have been consistently found in recent applications. For example, PubChem is a real database of chemical molecules, which can be freely accessed via its web interface, for its clients to query chemical compounds. Another example, namely Daylight, delivers chemistry and chemical informatics technologies to life science companies and recently, it has provided web services to allow clients to access its technologies via a network. Subgraph query (via subgraph isomorphism), which is a fundamental and powerful query in various real graph applications, has actively been investigated for performance enhancements recently. However, due to the high complexity of subgraph query, hosting efficient subgraph query services has been a technically challenging task, because the owners of graph data may not always possess the information technology (IT) expertise to offer such services and hence may outsource to query service providers (SP). SPs are often equipped with high performance computing utilities (e.g., a cloud) that offer better scalability, elasticity and IT management. Unfortunately, as SPs may not always be trusted, security (such as the confidentiality of messages exchanged) has been recognized as one of the critical attributes of Quality of Services (QoS). This directly influences the willingness of both data owners and query clients to use SP's services. In the past decade, there is a bloom on the research on query processing with privacy preservation, for example, in the context of relational databases, spatial databases and graph databases. However, up to date, the problem of efficient private subgraph query has not yet been solved.
Therefore, it is an objective of the present invention is to provide solution to structure-preserving subgraph queries that is both efficient and private. The present invention solves structure preservations at two levels. The first level is termed structure-preserving subgraph query processing (SPQP) which preserves the structures of both subgraph queries and data graphs. The second level is termed asymmetric structure-preserving subgraph query processing (ASPQP) which preserves only the structure of subgraph queries. For ease of exposition, one shall present the present invention for SPQP and that for ASPQP separately.
Citation or identification of any reference in this section or any other section of this application shall not be construed as an admission that such reference is available as prior art for the present application.